#include <bits/stdc++.h>
#define gc getchar
#define pc putchar
#define pt printf
#define IL inline
#define int long long
#define For(i,a,b) for(int i=a;i<=b;++i)
#define Rof(i,a,b) for(int i=a;i>=b;++i) 
using namespace std;
const int Mxk=4e6+5;
int P,T,N,M,K,Ans,Sum,Fc[Mxk],Iv[Mxk];
int _() {
	int x=0,f=0;char ch=gc();
	while(ch<'0'||ch>'9') f|=(ch=='-'),ch=gc();
	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=gc();
	return f?-x:x;
}
void __(int x) {
	int stk[30],tp=0;
	if(x<0) x=-x,pc('-');
	do stk[++tp]=x%10,x/=10;while(x);
	while(tp) pc(stk[tp--]^48);
}
void Init() {
	Fc[0]=Iv[0]=Fc[1]=Iv[1]=1;
	For(i,2,Mxk-1) {
		Fc[i]=Fc[i-1]*i%P,Iv[i]=(P-P/i)*Iv[P%i]%P;
	}
	For(i,1,Mxk-1) (Iv[i]*=Iv[i-1])%=P;
}
int Power(int x,int b) {
	int s=1;
	while(b) {
		if(b&1) (s*=x)%=P;
		(x*=x)%=P,b>>=1; 
	}
	return s;
}
int C(int x,int y) {return Fc[x]*Iv[y]%P*Iv[x-y]%P;}
void Upd(int &x,int y) {x=x+y<P?x+y:x+y-P;}
/*
998244353
1 3 4
*/
signed main() {
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	P=_(),T=_();
	Init();
	while(T--) {
		N=_(),M=_();
		K=N*M,Ans=0,Sum=1;
		For(i,1,K) {
			int Res=0;
			For(k,1,min(i,N)) Upd(Res,C(i-1,k-1)*C(N,k));
			Upd(Ans,Res*Sum);
			pt("[%lld] Res=%lld Sum=%lld\n",i,Res,Sum);
			Upd(Sum,Res);
		}
//		For(i,1,K) {
//			int Res=C(N+i-1,N-1);
//			Upd(Ans,Res*Sum%P);
//			pt("[%lld] Res=%lld Sum=%lld\n",i,Res,Sum);
//			Upd(Sum,Res);
//		}
		int Tot=Power(M+1,N<<1);
		pt("Ans=%lld Tot=%lld\n",Ans,Tot);
		pt("_____________________");
		__(Ans*Power(Tot,P-2)%P),pc('\n');
	}
	return 0;
}
